import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

public class LeetCode994 {

    public static void main(String[] args) {
        int[][] grid = {{2, 1, 1}, {1, 1, 0} ,{0, 1, 1}};

        System.out.println(orangesRotting(grid));
    }

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, 1, -1};

    public static int orangesRotting(int[][] grid) {
        int R = grid.length;
        int C = grid[0].length;
        Queue<Integer> queue = new ArrayDeque<>();
        Map<Integer, Integer> depth = new HashMap<>();
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (grid[r][c] == 2) {
                    int code = r * C + c;
                    queue.add(code);
                    depth.put(code, 0);
                }
            }
        }
        int res = 0;
        while (!queue.isEmpty()) {
            int code = queue.remove();
            int r = code / C;
            int c = code % C;
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    int nCode = nr * C + nc;
                    queue.add(nCode);
                    depth.put(nCode, depth.get(code) + 1);
                    res = depth.get(nCode);
                }
            }
        }
        for (int[] row : grid) {
            for (int v : row){
                if (v == 1) {
                    return -1;
                }
            }
        }
        return res;
    }

}
